Conference Proceedings
Towards an Optimal Outdoor Advertising Placement: When a Budget Constraint Meets Moving Trajectories
P Zhang, Z Bao, Y Li, G Li, Y Zhang, Z Peng
ACM Transactions on Knowledge Discovery from Data | ASSOC COMPUTING MACHINERY | Published : 2020
DOI: 10.1145/3350488
Abstract
In this article, we propose and study the problem of trajectory-driven influential billboard placement: given a set of billboards U (each with a location and a cost), a database of trajectories T, and a budget L, we find a set of billboards within the budget to influence the largest number of trajectories. One core challenge is to identify and reduce the overlap of the influence from different billboards to the same trajectories, while keeping the budget constraint into consideration. We show that this problem is NP-hard and present an enumeration based algorithm with (1-1/e) approximation ratio. However, the enumeration would be very costly when |U| is large. By exploiting the locality prop..
View full abstractGrants
Awarded by Appalachian Regional Commission
Funding Acknowledgements
Ping Zhang was supported by National Key Research & Development Program of China (No. 2018YFB1003400). Zhiyong Peng was supported by the Ministry of Science and Technology of China (2016YFB1000700) and National Key Research & Development Program of China (No. 2018YFB1003402). Zhifeng Bao was supported by ARC (DP170102726 and DP180102050), NSFC (61728204, 91646204), and was a recipient of Google Faculty Award. Guoliang Li was supported by the 973 Program of China (2015CB358700), NSFC (61632016, 61472198, 61521002, and 61661166012), and TAL education. Yuchen was supported by the Singapore MOE Tier 1 grant MSS18C001.